[[Coding theory MOC]]
# Linear code

A $q$-ary **linear code** of length $n$ and dimension $k$ is a $k$-[[Dimension of a vector space|dimensional]] [[vector subspace]] $\mathcal{C} \leq \mathbb{K}_{q}^n$, #m/def/code
where $\mathbb{K}_{q}$ is the [[Galois field]] of order $q$.
Thus it is a particular kind of [[code]] of length $n$ in the alphabet $\mathbb{K}_{q}$.
Following [[@vanlintIntroductionCodingTheory1999|van Lint]], a $k$-dimensional linear code of length $n$ and [[code#^minimumDistance]] $d$ is called an **$[n,k,d]$ code**, where the $d$ is optional.[^1999]
Of particular interest are [[Binary linear code|binary linear codes]].

## Further notions

- A code is **degenerate** iff some digit is zero for all codewords.
- $\mathbb{K}_{q}^n$ is equipped with a natural [[Bilinear form#^nondegenerate]] [[Bilinear form#^symmetric]] [[bilinear form]]
  $$
  \begin{align*}
  \vab x \cdot \vab y = \tp{\vab x} \vab y = \sum_{i=1}^n x_{i}y_{i}
  \end{align*}
  $$
  which is used to define the [[Orthogonal code]].
- A **generator matrix** $A$ has $\mathcal{C}$ as its [[Row and column space|row space]], and is said to be in **standard form** iff it is in [[Row echelon form|reduced row echelon form]] $A = [\mathbb{1}_{k} \mid P]$. The first $k$ digits are thence **information digits** and the latter are **parity check digits**.
  Every code is equivalent to one generated by such a standard form matrix.
  ^generator
- The generator matrix $H = [-\tp P \mid \mathbb{1}_{k}]$ of the [[Orthogonal code]] is called the **parity check matrix**, since $x \in \mathcal{C} \iff x \tp H = \vab 0$. ^check
- The value of $\opn{syn} x = x \tp H$ is called the **syndrome** of $x$. Syndromes uniquely label **cosets** $K_{\opn{syn}x} \in\mathbb{K}_{q}^n / \mathcal{C}$ in the [[Quotient vector space|quotient]]. ^syndrome
- In a given coset $K_{\opn{syn}x} \in \mathbb{K}_{q}^n / \mathcal{C}$ a minimum weight string $l_{\opn{syn} x} \in K_{\opn{syn} x}$ is called a **coset leader**, and the correction of a string $x$ is $x - l_{\opn{syn}x}$. 
  Thus a [[perfect code]] has unique coset leaders. ^leader
- [[Linear equivalence of codes]]

  [^1999]: 1999\. [[Sources/@vanlintIntroductionCodingTheory1999|Introduction to coding theory]], §3.2, pp. 35–36

## Properties

- The [[Code#^rate]] of a $[n,k]$-code is $n / k$.
- The [[Code#^minimumDistance]] of a linear code is its [[Code#^minimumWeight]].

## Special kinds of linear code

- [[Projective code]]

## See also

- [[Extended code]]

#
---
#state/tidy | #lang/en | #SemBr